#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int Datatype;
typedef struct Stack
{
	Datatype* arr;
	int top;
	int capacity;
}ST;

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void STDesTory(ST* ps)
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
		ps->arr = NULL;
	}
	ps->top = ps->capacity = 0;

}

void STPush(ST* ps, Datatype s)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		Datatype* tmp = (Datatype*)realloc(ps->arr, newCapacity * sizeof(Datatype));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	ps->arr[ps->top++] = s;

}

void STErase(ST* ps)
{
	assert(ps && ps->top);
	ps->top--;
}

Datatype STTop(ST* ps)
{
	assert(ps && ps->top);
	return ps->arr[ps->top - 1];
}

Datatype STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}


typedef struct {
	ST PushST;
	ST PopST;
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&pq->PushST);
	STInit(&pq->PopST);
	return pq;
}

bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}

void myQueuePush(MyQueue* obj, int x) {
	STPush(&obj->PushST, x);
}

int myQueuePop(MyQueue* obj) {
	if (StackEmpty(&obj->PopST))
	{
		while (!StackEmpty(&obj->PushST))
		{
			STPush(&obj->PopST, STTop(&obj->PushST));
			STErase(&obj->PushST);
		}
	}
	int a = STTop(&obj->PopST);
	STErase(&obj->PopST);
	return a;
}

int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(&obj->PopST))
	{
		while (!StackEmpty(&obj->PushST))
		{
			STPush(&obj->PopST, STTop(&obj->PushST));
			STErase(&obj->PushST);
		}
	}
	return STTop(&obj->PopST);
}



void myQueueFree(MyQueue* obj) {
	STDesTory(&obj->PushST);
	STDesTory(&obj->PopST);
	free(obj);
	obj = NULL;

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/